package week_six;

import java.util.Arrays;

public class BestTimeToBuyAndSellStockIV_188 {
    public int maxProfit(int c, int[] prices) {
        int Min_Value = (int)-1e9;

        int n = prices.length;
        int[] newPrices = new int[n+1];
        for(int i=1;i<=n;i++) newPrices[i]=prices[i-1];

        int[][][] f = new int[2][2][c+1];
        for(int i=0;i<n;i++){
            Arrays.fill(f[i&1][0], Min_Value);
            Arrays.fill(f[i&1][1], Min_Value);
        }
        f[0][0][0]=0;

        for(int i=0;i<n;i++)
            for(int j=0;j<=1;j++)
                for(int k=0;k<=c;k++){
                    if(j==0&&k<c) f[(i+1)&1][1][k+1] = Math.max(f[(i+1)&1][1][k+1], f[i&1][j][k] - newPrices[i+1]);
                    if(j==1) f[(i+1)&1][0][k] = Math.max(f[(i+1)&1][0][k], f[i&1][j][k]+newPrices[i+1]);
                    // else
                    f[(i+1)&1][j][k]=Math.max(f[(i+1)&1][j][k],f[i&1][j][k]);
                    // System.out.println(f[i][0][k]);
                }

        int ans = 0;
        for(int k=0;k<=c;k++){
            ans = Math.max(ans, f[n&1][0][k]);
        }
        return ans;
    }

}
